#include "GM3Graph.h"

#include "KDTree.h"

#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
using namespace std;
//using namespace GM3;

bool compareEdge(GM3Graph::edge e1, GM3Graph::edge e2);

GM3Graph::GM3Graph(const char *fn):
    nodes(), edges(), kd(NULL)
{
    loadFromFile(fn);
}

GM3Graph::GM3Graph(vector<node> n, vector<edge> e):
    nodes(), edges(), kd(NULL)
{
    loadFromPassed(n, e);
}

GM3Graph::~GM3Graph(){
    if(kd) delete kd;
}


void GM3Graph::getNodePositions(float *b){
    for(unsigned int i=0; i<numNodes(); i++){
        b[i*2+0] = nodes[i].p.x();
        b[i*2+1] = nodes[i].p.y();
    }
}

void GM3Graph::setNodePositions(float *b){
    for(unsigned int i=0; i<numNodes(); i++){
        nodes[i].p.x(b[i*2+0]);
        nodes[i].p.y(b[i*2+1]);
    }
}

void GM3Graph::getNodeWeights(float *b){
    for(unsigned int i=0; i<numNodes(); i++) b[i] = nodes[i].weight;
}

void GM3Graph::getEdgeWeights(float *b){
    for(unsigned int i=0; i<numEdges(); i++) b[i] = edges[i].weight;
}


void GM3Graph::loadFromPassed(vector<node> n, vector<edge> e){
    //load the nodes & edges
    nodes = n;
    edges = e;

    formatLoadedData();
}

void GM3Graph::loadFromFile(const char *filename){
    if(!filename) return;

    string fn(filename);
    string ext = fn.substr(fn.find_last_of('.')+1);
    int ret = 0;

    if(ext.compare("nod") == 0) ret = loadNodEdg(fn);
    else if(ext.compare("mtx") == 0) ret = loadMTX(fn);

    if(ret) formatLoadedData();
}

int GM3Graph::loadNodEdg(string nfn){
    string efn = nfn.substr(0, nfn.find_last_of('.')).append(".edg");
    return loadNodeFile(nfn.c_str()) && loadEdgeFile(efn.c_str());
}

int GM3Graph::loadNodeFile(string fn){
    stringstream l;
    char buf[buffsize];

    int id = 0;
    string name;
    ifstream nodefile(fn.c_str());
    if(!nodefile.is_open()){ //check file open success
        cerr << "Could not open node file \"" << fn << "\"" << endl;
        return 0;
    }

    nodefile.getline(buf, buffsize);
    while(!nodefile.eof()){
        l << buf;
        l >> id >> name;
        nodes.push_back(node(cvec(), name, 1.f, -1, id));
        l.str(""); l.clear();
        nodefile.getline(buf, buffsize);
    }
    nodefile.close();

    return 1;
}

int GM3Graph::loadEdgeFile(string fn){
    stringstream l;
    char buf[buffsize];

    vector<bool> edgeExists(nodes.size()*nodes.size(), false);

    int id1 = 0, id2 = 0;
    float weight = 0.0;
    ifstream edgefile(fn.c_str());
    if(!edgefile.is_open()){ //check file open success
        cerr << "Could not open edge file \"" << fn << "\"" << endl;
        return 0;
    }

    edgefile.getline(buf, buffsize);
    while(!edgefile.eof()){
        l << buf;
        l >> id1 >> id2 >> weight;
        if(id1 != id2){
            edges.push_back(edge(id1-1, id2-1, weight));
            edgeExists[(id1-1)*numNodes() + (id2-1)] = true;
        }
        l.str(""); l.clear();
        edgefile.getline(buf, buffsize);
    }
    edgefile.close();

    return 1;
}

void GM3Graph::skip(ifstream &in, char c){
    while(in.good() && in.peek() == c) in.ignore();
}

int GM3Graph::processMTXHeader(ifstream &f){
    string object, format, qualifier;
    f.ignore(buffsize, ' '); //skip %%MatrixMarket
    int vals = 0;

    //grab the object
    skip(f, ' ');
    object.resize(7); //size of longest acceptable object - "matrix"
    getline(f, object, ' ');
    if(object.compare("matrix") != 0){
        cout << "Refusing to load file: object type is not 'matrix'" << endl;
        return 0;
    }

    //grab the format
    skip(f, ' ');
    format.resize(11); //size of longest acceptable format - "coordinate"
    getline(f, format, ' ');
    if(format.compare("coordinate") != 0){
        cout << "Refusing to load file: format type is not 'coordinate'" <<
            endl;
        return 0;
    }

    //grab the first qualifier
    skip(f, ' ');
    qualifier.resize(15); //size of longest qualifier - "skew-symmetric"
    getline(f, qualifier, ' ');
    if(qualifier.compare("pattern") == 0) vals = 2;
    else if(qualifier.compare("real") == 0) vals = 3;
    else if(qualifier.compare("integer") == 0) vals = 3;
    else if(qualifier.compare("complex") == 0) vals = 4;

    //leave the pointer on the next line
    f.ignore(buffsize, '\n');

    if(!vals) cout << "Refusing to load file: unrecognized qualifier: " <<
        qualifier << endl;

    return vals;
}

int GM3Graph::processMTXComments(ifstream &f){
    while(f.good() && f.peek() == '%') f.ignore(buffsize, '\n'); //skip comments

    return f.good();
}

int GM3Graph::processMTXStats(ifstream &f, unsigned int &n, unsigned int &e){
    unsigned int rows, columns, entries;
    rows = columns = entries = 0;

    skip(f, ' ');
    f >> rows;
    skip(f, ' ');
    f >> columns;
    skip(f, ' ');
    f >> entries;

    //leave the pointer on the next line
    f.ignore(buffsize, '\n');

    if(rows == 0 || columns == 0 || entries == 0){
        cout << "Could not load file: matrix statistics indicate empty matrix."
            << endl;
        return 0;
    }

    if(rows != columns){
        cout << "Could not load file: matrix dimensions not square." << endl;
        return 0;
    }

    n = rows;
    e = entries;
    return 1;
}

void GM3Graph::createBlankNodes(unsigned int N){
    nodes = vector<node> (N, node());
}

void GM3Graph::fileCleanup(ifstream &f){
    f.close();
}

int GM3Graph::processMTXPatternLines(ifstream &f, unsigned int N, unsigned int E){
    //create the nodes
    createBlankNodes(N);

    edges.reserve(E);
    for(unsigned int i=0; f.good() && i < E; i++){
        edges.push_back(edge());
        f >> edges[i].id1 >> edges[i].id2;
        edges[i].id1--;
        edges[i].id2--;
        f.ignore(buffsize, '\n');
    }

    return 1;
}

int GM3Graph::processMTXValuedLines(ifstream &f, unsigned int N, unsigned int E){
    //create the nodes
    createBlankNodes(N);

    edges.reserve(E);
    for(unsigned int i=0; f.good() && i < E; i++){
        edges.push_back(edge());
        //read in and ignore the edge value
        f >> edges[i].id1 >> edges[i].id2;
        edges[i].id1--;
        edges[i].id2--;
        f.ignore(buffsize, '\n');
    }

    return 1;
}


int GM3Graph::loadMTX(string fn){
    ifstream f(fn.c_str());
    if(!f.is_open()){ //check file open success
        cerr << "Could not open file \"" << fn << "\"" << endl;
        return 0;
    }

    unsigned int entL; //entries per line - 2 if integer, 1 if pattern
    unsigned int N, E; //number of nodes, edges

    if( !(entL = processMTXHeader(f)) ){ fileCleanup(f); return 0; }
    if( !processMTXComments(f)){ fileCleanup(f); return 0; }
    if( !processMTXStats(f, N, E)){ fileCleanup(f); return 0; }

    int ret = 0;
    if(entL == 2) ret = processMTXPatternLines(f, N, E);
    else ret = processMTXValuedLines(f, N, E);

    fileCleanup(f);
    return ret;
}


void GM3Graph::formatLoadedData(){
    //remove edges that are to & frome the same node, and create a temp
    //edge matrix
    vector<bool> edgeExists(nodes.size()*nodes.size(), false);
    for(vector<edge>::iterator i=edges.begin(); i<edges.end(); i++){
        if( (*i).id1 == (*i).id2 ) edges.erase(i);
        else edgeExists[((*i).id1)*numNodes() + ((*i).id2)] = true;
    }

    //make sure all reverse edges exist
    int initialEdges = numEdges();
    for(int i=0; i<initialEdges; i++){
        if(!edgeExists.at(edges[i].id2*numNodes() + edges[i].id1))
            edges.push_back(edge(edges[i].id2, edges[i].id1, edges[i].weight));
    }

    //randomize();   //0308 1144 yuhsuan debug
}

bool compareEdge(GM3Graph::edge e1, GM3Graph::edge e2){
    return e1.id1 < e2.id1 || ( e1.id1==e2.id1 && e1.id2<e2.id2 ); 
}
void GM3Graph::sortEdges(){
    sort(edges.begin(), edges.end(), compareEdge);
}

void GM3Graph::randomize(){
    //distribute the points randomly
    //cout << "[debug] GM3Graph::randomize()" << endl;
    srand(time(NULL));

    if(nodes.empty()) return;

    for(int i=0; i<(int)nodes.size(); i++){
        nodes[i].p.x( (float)rand() / (float)RAND_MAX );
        nodes[i].p.y( (float)rand() / (float)RAND_MAX );
    }

    rescale();

    //reorder the nodes
    //std::vector
}

void GM3Graph::boundingBox(float &x0, float &y0, float &x1, float &y1){
    //find the lower left of the bounding box
    x0 = x1 = nodes[0].p.x();
    y0 = y1 = nodes[0].p.y();
    for(unsigned int i=1; i<numNodes(); i++){
        x0 = nodes[i].p.x() < x0 ? nodes[i].p.x() : x0;
        y0 = nodes[i].p.y() < y0 ? nodes[i].p.y() : y0;

        x1 = nodes[i].p.x() > x1 ? nodes[i].p.x() : x1;
        y1 = nodes[i].p.y() > y1 ? nodes[i].p.y() : y1;
    }
}

void GM3Graph::rescale(){
    //find the lower left of the bounding box
    float x = nodes[0].p.x();
    float y = nodes[0].p.y();
    for(unsigned int i=1; i<numNodes(); i++){
        x = nodes[i].p.x() < x ? nodes[i].p.x() : x;
        y = nodes[i].p.y() < y ? nodes[i].p.y() : y;
    }

    //shift the the graph to the lower left of the first quadrant
    for(unsigned int i=0; i<numNodes(); i++){
        nodes[i].p.x(nodes[i].p.x() - x);
        nodes[i].p.y(nodes[i].p.y() - y);
    }

    //find the upper right of the bounding box
    x = nodes[0].p.x();
    y = nodes[0].p.y();
    for(unsigned int i=1; i<numNodes(); i++){
        x = nodes[i].p.x() > x ? nodes[i].p.x() : x;
        y = nodes[i].p.y() > y ? nodes[i].p.y() : y;
    }

    //scale the graph to the [0,1] box
    if(x > 0.f)
        for(unsigned int i=0; i<numNodes(); i++) nodes[i].p.x(nodes[i].p.x()/x);
    if(y > 0.f)
        for(unsigned int i=0; i<numNodes(); i++) nodes[i].p.y(nodes[i].p.y()/y);
}


GM3Graph *GM3Graph::maxIndptSet(){
    using namespace std;

    sortEdges();

    GM3Graph *par = new GM3Graph();
    bool visited[numNodes()];
    memset(visited, false, sizeof(bool)*numNodes());
    unsigned int ind = 0;
    unsigned int s = 0;
    unsigned int t = 0;

    //choose the nodes for the parent graph
    while(ind < nodes.size()){
        if(visited[ind]){
            ind++;
            continue;
        }

        //add this node
        visited[ind] = true;
        par->addNode(nodes[ind]);
        nodes[ind].parent = par->numNodes()-1;

        //determine adjacency list bounds
        s = t;
        while(s < edges.size() && edges[s].id1 < ind) s++;
        t = s;
        while(t < edges.size() && edges[t].id1 == ind) t++;

        //remove all adjacent nodes from consideration for the parent graph
        for(unsigned int i=s; i<t; i++){ 
            unsigned int rind = edges[i].id2;
            if(!visited[rind]){
                nodes[rind].parent = nodes[ind].parent;
                par->nodes[nodes[rind].parent].weight += nodes[rind].weight;
                visited[rind] = true;
            }
        }

        ind++;
    }

    //For each edge, add it to the MIS if the nodes' parents differ.
    for(unsigned int i=0; i<edges.size(); i++){
        unsigned int p1 = nodes[edges[i].id1].parent;
        unsigned int p2 = nodes[edges[i].id2].parent;
        float w = edges[i].weight;
        if( p1 != p2 ) par->addEdge(edge(p1, p2, w));
    }
    
    //sort
    par->sortEdges();

    //mark the duplicate edges
    vector<bool> edgeAccept(par->edges.size(), true);
    for(unsigned int i=1; i<par->edges.size(); i++){
        if( edgeEqual(par->edges[i-1], par->edges[i]) ){
            edgeAccept[i-1] = false;
            par->edges[i].weight += par->edges[i-1].weight;
        }
    }

    unsigned int sz = 0;
    //find first unaccepted edge
    while(sz < edgeAccept.size() && edgeAccept[sz]) sz++;

    //condense the list
    for(unsigned int i=sz+1; i<par->edges.size(); i++){
        if(edgeAccept[i]) par->edges[sz++] = par->edges[i];
    }

    par->edges.resize(sz);

    return par;
}

void GM3Graph::setLayoutFromMIS(GM3Graph *g, float jitter){
    for(unsigned int i=0; i<numNodes(); i++){
        nodes[i].p = g->nodeAt(nodes[i].parent).p;
    }

    srand(time(NULL));
    for(int i=0; i<(int)nodes.size(); i++){
        nodes[i].p.x(nodes[i].p.x() + jitter*(float)rand()/(float)RAND_MAX );
        nodes[i].p.y(nodes[i].p.y() + jitter*(float)rand()/(float)RAND_MAX );
    }
}

std::vector<unsigned int> GM3Graph::buildKDTree(){
    if(!kd) kd = new KDTree(this);
    return kd->buildTree();
}

std::vector<unsigned int> GM3Graph::buildKDTree(unsigned int thresh){
    if(!kd) kd = new KDTree(this);
    return kd->buildTree(thresh);
}


void GM3Graph::translateEdges(std::vector<unsigned int> &trans){
    for(unsigned int i=0; i<edges.size(); i++){
        edges[i].id1 = trans.at(edges[i].id1);
        edges[i].id2 = trans.at(edges[i].id2);
    }
}

void GM3Graph::translateParents(std::vector<unsigned int> &trans){
    for(unsigned int i=0; i<nodes.size(); i++){
        if(nodes[i].parent >= 0 && nodes[i].parent < (int)(trans.size()))
            nodes[i].parent = trans.at(nodes[i].parent);
    }
}
